package 二叉树的层序遍历;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author: zhengtao
 * @description: N叉树的层序遍历
 * 给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。
 * 树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。
 * @version: 1.0
 * @date: 2022/10/29  14:37
 */
public class Demo429 {

// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
    public List<List<Integer>> levelOrder(Node root) {
         List<List<Integer>> res=new ArrayList<>();
         if(root==null){
              return res;
         }
         Queue<Node> queue=new LinkedList();
         queue.add(root);
         while (!queue.isEmpty()){
             int size=queue.size();
             List<Integer> temp=new ArrayList<>();
             while (size-->0){
                 Node poll = queue.poll();
                 temp.add(poll.val);
                 List<Node> children = poll.children;
                 //添加子节点
                 for (Node child : children) {
                     if (child!=null){
                         queue.add(child);
                     }
                 }
             }
             res.add(temp);
         }
          return res;
    }

}
